{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The Score of Students Solving Math Expression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #memoization #array #math #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #记忆化搜索 #数组 #数学 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: scoreOfStudents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #解出数学表达式的学生分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，它 <strong>只</strong> 包含数字&nbsp;<code>0-9</code>&nbsp;，加法运算符&nbsp;<code>'+'</code>&nbsp;和乘法运算符&nbsp;<code>'*'</code>&nbsp;，这个字符串表示一个&nbsp;<strong>合法</strong>&nbsp;的只含有&nbsp;<strong>个位数</strong><strong>数字</strong>&nbsp;的数学表达式（比方说&nbsp;<code>3+5*2</code>）。有 <code>n</code>&nbsp;位小学生将计算这个数学表达式，并遵循如下 <strong>运算顺序</strong>&nbsp;：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>按照 <strong>从左到右</strong>&nbsp;的顺序计算 <strong>乘法</strong>&nbsp;，然后</li>\n",
    "\t<li>按照 <strong>从左到右</strong>&nbsp;的顺序计算 <strong>加法</strong>&nbsp;。</li>\n",
    "</ol>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>answers</code>&nbsp;，表示每位学生提交的答案。你的任务是给 <code>answer</code>&nbsp;数组按照如下 <strong>规则</strong>&nbsp;打分：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果一位学生的答案 <strong>等于</strong>&nbsp;表达式的正确结果，这位学生将得到 <code>5</code>&nbsp;分。</li>\n",
    "\t<li>否则，如果答案由&nbsp;<strong>一处或多处错误的运算顺序</strong>&nbsp;计算得到，那么这位学生能得到 <code>2</code>&nbsp;分。</li>\n",
    "\t<li>否则，这位学生将得到 <code>0</code>&nbsp;分。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回所有学生的分数和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/17/student_solving_math.png\" style=\"width: 678px; height: 109px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"7+3*1*2\", answers = [20,13,42]\n",
    "<b>输出：</b>7\n",
    "<b>解释：</b>如上图所示，正确答案为 13 ，因此有一位学生得分为 5 分：[20,<em><strong>13</strong></em>,42] 。\n",
    "一位学生可能通过错误的运算顺序得到结果 20 ：7+3=10，10*1=10，10*2=20 。所以这位学生得分为 2 分：[<em><strong>20</strong></em>,13,42] 。\n",
    "所有学生得分分别为：[2,5,0] 。所有得分之和为 2+5+0=7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"3+5*2\", answers = [13,0,10,13,13,16,16]\n",
    "<b>输出：</b>19\n",
    "<b>解释：</b>表达式的正确结果为 13 ，所以有 3 位学生得到 5 分：[<em><strong>13</strong></em>,0,10,<em><strong>13</strong></em>,<em><strong>13</strong></em>,16,16] 。\n",
    "学生可能通过错误的运算顺序得到结果 16 ：3+5=8，8*2=16 。所以两位学生得到 2 分：[13,0,10,13,13,<em><strong>16</strong></em>,<em><strong>16</strong></em>] 。\n",
    "所有学生得分分别为：[5,0,0,5,5,2,2] 。所有得分之和为 5+0+0+5+5+2+2=19 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"6+0*1\", answers = [12,9,6,4,8,6]\n",
    "<b>输出：</b>10\n",
    "<b>解释：</b>表达式的正确结果为 6 。\n",
    "如果一位学生通过错误的运算顺序计算该表达式，结果仍为 6 。\n",
    "根据打分规则，运算顺序错误的学生也将得到 5 分（因为他们仍然得到了正确的结果），而不是 2 分。\n",
    "所有学生得分分别为：[0,0,5,0,0,5] 。所有得分之和为 10 分。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= s.length &lt;= 31</code></li>\n",
    "\t<li><code>s</code>&nbsp;表示一个只包含&nbsp;<code>0-9</code>&nbsp;，<code>'+'</code>&nbsp;和&nbsp;<code>'*'</code>&nbsp;的合法表达式。</li>\n",
    "\t<li>表达式中所有整数运算数字都在闭区间&nbsp;<code>[0, 9]</code>&nbsp;以内。</li>\n",
    "\t<li><code>1 &lt;=</code>&nbsp;数学表达式中所有运算符数目（<code>'+'</code> 和&nbsp;<code>'*'</code>）&nbsp;<code>&lt;= 15</code></li>\n",
    "\t<li>测试数据保证正确表达式结果在范围&nbsp;<code>[0, 1000]</code>&nbsp;以内。</li>\n",
    "\t<li><code>n == answers.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= answers[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-score-of-students-solving-math-expression](https://leetcode.cn/problems/the-score-of-students-solving-math-expression/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-score-of-students-solving-math-expression](https://leetcode.cn/problems/the-score-of-students-solving-math-expression/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"7+3*1*2\"\\n[20,13,42]', '\"3+5*2\"\\n[13,0,10,13,13,16,16]', '\"6+0*1\"\\n[12,9,6,4,8,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        target = eval(s)\n",
    "        n = len(s)\n",
    "        dp = defaultdict(lambda: defaultdict(set))\n",
    "        for i in range(0, n, 2):\n",
    "            dp[i][i].add(int(s[i]))\n",
    "        \n",
    "        for span in range(3, n + 1, 2):\n",
    "            for l in range(0, n - span + 1, 2):\n",
    "                r = l + span - 1\n",
    "                for mid in range(l + 1, r, 2):\n",
    "                    v1 = dp[l][mid-1]\n",
    "                    v2 = dp[mid+1][r]\n",
    "                    for a in v1:\n",
    "                        for b in v2:\n",
    "                            if s[mid] == '*' and a * b <= 1000:\n",
    "                                dp[l][r].add(a*b)\n",
    "                            if s[mid] == '+' and a + b <= 1000:\n",
    "                                dp[l][r].add(a+b)\n",
    "        \n",
    "        ans = 0\n",
    "        for a in answers:\n",
    "            if a == target:\n",
    "                ans += 5\n",
    "            elif a in dp[0][n-1]:\n",
    "                ans += 2\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def scoreOfStudents(self, s, answers):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type answers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)  # 表达式长度\n",
    "        # 计算正确答案\n",
    "        stack = [int(s[0])]\n",
    "        i = 1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]==\"*\":\n",
    "                pre = stack.pop()\n",
    "                stack.append(pre*int(s[i+1]))\n",
    "            else:\n",
    "                stack.append(int(s[i+1]))\n",
    "        true_ans = sum(stack)\n",
    "        \n",
    "        # 表达式中包含的数字数量\n",
    "        size = (n+1)//2     \n",
    "        # 状态空间： dp[i][j] 表示第i个数字-第j个数字（包含首位）的表达式的可能取值\n",
    "        dp = [[set() for _ in range(size)] for _ in range(size)] \n",
    "        for i in range(size):\n",
    "            dp[i][i] = [int(s[2*i])]\n",
    "\n",
    "        for k in range(2,size+1):     \n",
    "            # 区间长度 k:  取值 [2,size] （size=1于上文已经考虑）\n",
    "            for i in range(size-k+1): \n",
    "                # 区间开始位置 i, 对应区间 [i,i+k-1]; i 取值范围 [0,(size-k)]，\n",
    "                for j in range(i,i+k-1):    \n",
    "                    # 区间分割点j ,将区间分割为 [i,j]和[j+1,i+k-1] ； j取值为 [i,i+k-2]\n",
    "                    lst1 = dp[i][j]        #区间1可能取值\n",
    "                    lst2 = dp[j+1][i+k-1]  #区间1可能取值\n",
    "                    for e1 in lst1:\n",
    "                        for e2 in lst2:\n",
    "                            if s[2*j+1]==\"+\" and e1+e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1+e2)\n",
    "                            elif s[2*j+1]==\"*\" and e1*e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1*e2)\n",
    "        \n",
    "        # 分数计算\n",
    "        dic = defaultdict(int)\n",
    "        res = 0\n",
    "        for ans in answers:\n",
    "            if ans==true_ans:\n",
    "               res += 5\n",
    "            else:\n",
    "                dic[ans] += 1 \n",
    "\n",
    "        for k,v in dic.items():\n",
    "            if k in dp[0][size-1]:\n",
    "                res += 2*v\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        target=eval(s)\n",
    "        print(target)\n",
    "        n=len(s)\n",
    "        # dp[l][r]表示区间[l,r]能通过不同顺序计算出的结果\n",
    "        dp=defaultdict(lambda:defaultdict(set))\n",
    "        for i in range(0,n,2):\n",
    "            dp[i][i].add(int(s[i]))\n",
    "        \n",
    "        \n",
    "        for span in range(3,n+1,2):\n",
    "            for l in range(0,n-span+1,2):\n",
    "                r=l+span-1\n",
    "                for mid in range(l+1,r,2):\n",
    "                    v1=dp[l][mid-1]\n",
    "                    v2=dp[mid+1][r]\n",
    "                    for a in v1:\n",
    "                        for b in v2:\n",
    "                            if s[mid]=='*' and a*b<=1000:\n",
    "                                dp[l][r].add(a*b)\n",
    "                            if s[mid]=='+' and a+b<=1000:\n",
    "                                dp[l][r].add(a+b)\n",
    "        \n",
    "        res=0\n",
    "        for a in answers:\n",
    "            if a==target:\n",
    "                res+=5\n",
    "            elif a in dp[0][n-1]:\n",
    "                res+=2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        correct = eval(s)    #正确结果\n",
    "        n = len(s)    \n",
    "        dp = defaultdict(lambda: defaultdict(set))\n",
    "        print(dp)\n",
    "        for i in range(0, n, 2):\n",
    "            dp[i][i].add(int(s[i]))\n",
    "        print(dp)\n",
    "        \n",
    "        \n",
    "        # 步长\n",
    "        for step in range(0, n, 2):\n",
    "            # 左部分起始位置\n",
    "            for i in range(0, n - step, 2):\n",
    "                # 左部分长度\n",
    "                for t in range(0, step, 2):\n",
    "                    for x in dp[i][i + t]:\n",
    "                        for y in dp[i + t + 2][i + step]:\n",
    "                            z = 0\n",
    "                            if s[i + t + 1] == '*':\n",
    "                                z = x * y\n",
    "                            else:\n",
    "                                z = x + y\n",
    "                            if z <= 1000:\n",
    "                                dp[i][i + step].add(z)\n",
    "        ans = 0\n",
    "        for p in answers:\n",
    "            if p == correct:\n",
    "                ans += 5\n",
    "            elif p in dp[0][n - 1]:\n",
    "                ans += 2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def scoreOfStudents(self, s, answers):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type answers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)  # 表达式长度\n",
    "        # 计算正确答案\n",
    "        true_ans = eval(s)\n",
    "        \n",
    "        # 表达式中包含的数字数量\n",
    "        size = (n+1)//2     \n",
    "        # 状态空间： dp[i][j] 表示第i个数字-第j个数字（包含首位）的表达式的可能取值\n",
    "        dp = [[set() for _ in range(size)] for _ in range(size)] \n",
    "        for i in range(size):\n",
    "            dp[i][i] = [int(s[2*i])]\n",
    "            #print(dp[i])\n",
    "        #return\n",
    "        for k in range(2,size+1):     \n",
    "            # 区间长度 k:  取值 [2,size] （size=1于上文已经考虑）\n",
    "            for i in range(size-k+1): \n",
    "                # 区间开始位置 i, 对应区间 [i,i+k-1]; i 取值范围 [0,(size-k)]，\n",
    "                for j in range(i,i+k-1):    \n",
    "                    # 区间分割点j ,将区间分割为 [i,j]和[j+1,i+k-1] ； j取值为 [i,i+k-2]\n",
    "                    lst1 = dp[i][j]        #区间1可能取值\n",
    "                    lst2 = dp[j+1][i+k-1]  #区间1可能取值\n",
    "                    for e1 in lst1:\n",
    "                        for e2 in lst2:\n",
    "                            if s[2*j+1]==\"+\" and e1+e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1+e2)\n",
    "                            elif s[2*j+1]==\"*\" and e1*e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1*e2)\n",
    "        \n",
    "        #for i in range(size):\n",
    "            #print(dp[i])\n",
    "        #return\n",
    "        # 分数计算\n",
    "        res = 0\n",
    "        for ans in answers:\n",
    "            if ans==true_ans:\n",
    "               res += 5\n",
    "            elif ans in dp[0][size - 1]:\n",
    "                res += 2\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type answers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)  # 表达式长度\n",
    "        # 计算正确答案\n",
    "        stack = [int(s[0])]\n",
    "        i = 1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]==\"*\":\n",
    "                pre = stack.pop()\n",
    "                stack.append(pre*int(s[i+1]))\n",
    "            else:\n",
    "                stack.append(int(s[i+1]))\n",
    "        true_ans = sum(stack)\n",
    "        \n",
    "        # 表达式中包含的数字数量\n",
    "        size = (n+1)//2     \n",
    "        # 状态空间： dp[i][j] 表示第i个数字-第j个数字（包含首位）的表达式的可能取值\n",
    "        dp = [[set() for _ in range(size)] for _ in range(size)] \n",
    "        for i in range(size):\n",
    "            dp[i][i] = [int(s[2*i])]\n",
    "\n",
    "        for k in range(2,size+1):     \n",
    "            # 区间长度 k:  取值 [2,size] （size=1于上文已经考虑）\n",
    "            for i in range(size-k+1): \n",
    "                # 区间开始位置 i, 对应区间 [i,i+k-1]; i 取值范围 [0,(size-k)]，\n",
    "                for j in range(i,i+k-1):    \n",
    "                    # 区间分割点j ,将区间分割为 [i,j]和[j+1,i+k-1] ； j取值为 [i,i+k-2]\n",
    "                    lst1 = dp[i][j]        #区间1可能取值\n",
    "                    lst2 = dp[j+1][i+k-1]  #区间1可能取值\n",
    "                    for e1 in lst1:\n",
    "                        for e2 in lst2:\n",
    "                            if s[2*j+1]==\"+\" and e1+e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1+e2)\n",
    "                            elif s[2*j+1]==\"*\" and e1*e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1*e2)\n",
    "        \n",
    "        # 分数计算\n",
    "        dic = defaultdict(int)\n",
    "        res = 0\n",
    "        for ans in answers:\n",
    "            if ans==true_ans:\n",
    "               res += 5\n",
    "            else:\n",
    "                dic[ans] += 1 \n",
    "\n",
    "        for k,v in dic.items():\n",
    "            if k in dp[0][size-1]:\n",
    "                res += 2*v\n",
    "\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        correct = eval(s)    #正确结果\n",
    "        n = len(s)    \n",
    "        dp = defaultdict(lambda: defaultdict(set))\n",
    "        #print(dp)\n",
    "        #开空间，dp为n*n的数组，每一项为一个集合\n",
    "        for i in range(0, n, 2):\n",
    "            dp[i][i].add(int(s[i]))\n",
    "        #print(dp)\n",
    "        \n",
    "        \n",
    "        # 步长\n",
    "        for step in range(0, n, 2):\n",
    "            # 左部分起始位置\n",
    "            for i in range(0, n - step, 2):\n",
    "                # 左部分长度\n",
    "                for t in range(0, step, 2):\n",
    "                    # x是左半部分所有可能值\n",
    "                    # y是右半部分所有可能值\n",
    "                    for x in dp[i][i + t]:\n",
    "                        for y in dp[i + t + 2][i + step]:\n",
    "                            z = 0\n",
    "                            # 根据中间连接符是+/*，来计算连接后的值\n",
    "                            if s[i + t + 1] == '*':\n",
    "                                z = x * y\n",
    "                            else:\n",
    "                                z = x + y\n",
    "                            if z <= 1000:\n",
    "                                dp[i][i + step].add(z)\n",
    "                                #print(dp)\n",
    "        ans = 0\n",
    "        for p in answers:\n",
    "            if p == correct:\n",
    "                ans += 5\n",
    "            elif p in dp[0][n - 1]:\n",
    "                ans += 2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type answers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)  # 表达式长度\n",
    "        # 计算正确答案\n",
    "        stack = [int(s[0])]\n",
    "        i = 1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]==\"*\":\n",
    "                stack.append(stack.pop()*int(s[i+1]))\n",
    "            else:\n",
    "                stack.append(int(s[i+1]))\n",
    "        true_ans = sum(stack)\n",
    "        #true_ans = eval(s)\n",
    "\n",
    "        # 表达式中包含的数字数量\n",
    "        size = (n+1)//2     \n",
    "        # 状态空间： dp[i][j] 表示第i个数字-第j个数字（包含首位）的表达式的可能取值\n",
    "        dp = [[set() for _ in range(size)] for _ in range(size)] \n",
    "        for i in range(size):\n",
    "            dp[i][i] = [int(s[2*i])]\n",
    "\n",
    "        for k in range(2,size+1):     \n",
    "            # 区间长度 k:  取值 [2,size] （size=1于上文已经考虑）\n",
    "            for i in range(size-k+1): \n",
    "                # 区间开始位置 i, 对应区间 [i,i+k-1]; i 取值范围 [0,(size-k)]，\n",
    "                for j in range(i,i+k-1):    \n",
    "                    # 区间分割点j ,将区间分割为 [i,j]和[j+1,i+k-1] ； j取值为 [i,i+k-2]\n",
    "                    lst1 = dp[i][j]        #区间1可能取值\n",
    "                    lst2 = dp[j+1][i+k-1]  #区间1可能取值\n",
    "                    for e1 in lst1:\n",
    "                        for e2 in lst2:\n",
    "                            if s[2*j+1]==\"+\" and e1+e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1+e2)\n",
    "                            elif s[2*j+1]==\"*\" and e1*e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1*e2)\n",
    "        \n",
    "        # 分数计算\n",
    "        res = 0\n",
    "        for ans in answers:\n",
    "            if ans==true_ans:\n",
    "               res += 5\n",
    "            elif ans in dp[0][size-1]:\n",
    "                res += 2\n",
    "\n",
    "        \n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type answers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)  # 表达式长度\n",
    "        # 计算正确答案\n",
    "        stack = [int(s[0])]\n",
    "        i = 1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]==\"*\":\n",
    "                pre = stack.pop()\n",
    "                stack.append(pre*int(s[i+1]))\n",
    "            else:\n",
    "                stack.append(int(s[i+1]))\n",
    "        true_ans = sum(stack)\n",
    "        \n",
    "        # 表达式中包含的数字数量\n",
    "        size = (n+1)//2     \n",
    "        # 状态空间： dp[i][j] 表示第i个数字-第j个数字（包含首位）的表达式的可能取值\n",
    "        dp = [[set() for _ in range(size)] for _ in range(size)] \n",
    "        for i in range(size):\n",
    "            dp[i][i] = [int(s[2*i])]\n",
    "\n",
    "        for k in range(2,size+1):     \n",
    "            # 区间长度 k:  取值 [2,size] （size=1于上文已经考虑）\n",
    "            for i in range(size-k+1): \n",
    "                # 区间开始位置 i, 对应区间 [i,i+k-1]; i 取值范围 [0,(size-k)]，\n",
    "                for j in range(i,i+k-1):    \n",
    "                    # 区间分割点j ,将区间分割为 [i,j]和[j+1,i+k-1] ； j取值为 [i,i+k-2]\n",
    "                    lst1 = dp[i][j]        #区间1可能取值\n",
    "                    lst2 = dp[j+1][i+k-1]  #区间1可能取值\n",
    "                    for e1 in lst1:\n",
    "                        for e2 in lst2:\n",
    "                            if s[2*j+1]==\"+\" and e1+e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1+e2)\n",
    "                            elif s[2*j+1]==\"*\" and e1*e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1*e2)\n",
    "        \n",
    "        # 分数计算\n",
    "        #dic = defaultdict(int)\n",
    "        res = 0\n",
    "        for ans in answers:\n",
    "            if ans==true_ans:\n",
    "               res += 5\n",
    "            elif ans in dp[0][size-1]:\n",
    "                res += 2\n",
    "\n",
    "        \n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        # 计算实际的值\n",
    "        opd = []\n",
    "        i, n = 0, len(s)\n",
    "        while i < n:\n",
    "            if s[i] == '*':\n",
    "                i += 1\n",
    "                opd.append(opd.pop() * int(s[i]))\n",
    "            elif s[i] != '+':\n",
    "                opd.append(int(s[i]))\n",
    "            i += 1\n",
    "        real = sum(opd)\n",
    "        # 动态规划计算所有可能的解\n",
    "        dp = [[set() for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(0, n, 2):\n",
    "            dp[i][i].add(int(s[i]))  # 初始化长度为1的子表达式值\n",
    "        for width in range(3, n + 1, 2):  # 遍历所有子表达式的宽度\n",
    "            for left in range(0, n - width + 1, 2):  # 子表达式的左边界\n",
    "                right = left + width - 1  # 子表达式的右边界\n",
    "                for mid in range(left + 1, right, 2):  # 切分子表达式的操作符下标\n",
    "                    if s[mid] == '+':  # 计算dp[left][mid-1]、dp[mid+1][right]2个集合中所有元素的和\n",
    "                        for a in dp[left][mid - 1]:\n",
    "                            for b in dp[mid + 1][right]:\n",
    "                                if a + b <= 1000:  # 剪枝，可以筛掉很多\n",
    "                                    dp[left][right].add(a + b)\n",
    "                    else:  # 计算dp[left][mid-1]、dp[mid+1][right]2个集合中所有元素的乘积\n",
    "                        for a in dp[left][mid - 1]:\n",
    "                            for b in dp[mid + 1][right]:\n",
    "                                if a * b <= 1000:  # 剪枝，可以筛掉很多，不加这个筛选会超时\n",
    "                                    dp[left][right].add(a * b)\n",
    "        all = dp[0][n - 1]\n",
    "        # 计算结果\n",
    "        return sum(5 if a == real else (2 if a in all else 0) for a in answers)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type answers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)  # 表达式长度\n",
    "        # 计算正确答案\n",
    "        stack = [int(s[0])]\n",
    "        i = 1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]==\"*\":\n",
    "                stack.append(stack.pop()*int(s[i+1]))\n",
    "            else:\n",
    "                stack.append(int(s[i+1]))\n",
    "        true_ans = sum(stack)\n",
    "        \n",
    "        # 表达式中包含的数字数量\n",
    "        size = (n+1)//2     \n",
    "        # 状态空间： dp[i][j] 表示第i个数字-第j个数字（包含首位）的表达式的可能取值\n",
    "        dp = [[set() for _ in range(size)] for _ in range(size)] \n",
    "        for i in range(size):\n",
    "            dp[i][i] = [int(s[2*i])]\n",
    "\n",
    "        for k in range(2,size+1):     \n",
    "            # 区间长度 k:  取值 [2,size] （size=1于上文已经考虑）\n",
    "            for i in range(size-k+1): \n",
    "                # 区间开始位置 i, 对应区间 [i,i+k-1]; i 取值范围 [0,(size-k)]，\n",
    "                for j in range(i,i+k-1):    \n",
    "                    # 区间分割点j ,将区间分割为 [i,j]和[j+1,i+k-1] ； j取值为 [i,i+k-2]\n",
    "                    lst1 = dp[i][j]        #区间1可能取值\n",
    "                    lst2 = dp[j+1][i+k-1]  #区间1可能取值\n",
    "                    for e1 in lst1:\n",
    "                        for e2 in lst2:\n",
    "                            if s[2*j+1]==\"+\" and e1+e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1+e2)\n",
    "                            elif s[2*j+1]==\"*\" and e1*e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1*e2)\n",
    "        \n",
    "        # 分数计算\n",
    "        res = 0\n",
    "        for ans in answers:\n",
    "            if ans==true_ans:\n",
    "               res += 5\n",
    "            elif ans in dp[0][size-1]:\n",
    "                res += 2\n",
    "\n",
    "        \n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type answers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)  # 表达式长度\n",
    "        # 计算正确答案\n",
    "        stack = [int(s[0])]\n",
    "        i = 1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]==\"*\":\n",
    "                stack.append(stack.pop()*int(s[i+1]))\n",
    "            else:\n",
    "                stack.append(int(s[i+1]))\n",
    "        true_ans = sum(stack)\n",
    "        #true_ans = eval(s)\n",
    "\n",
    "        # 表达式中包含的数字数量\n",
    "        size = (n+1)//2     \n",
    "        # 状态空间： dp[i][j] 表示第i个数字-第j个数字（包含首位）的表达式的可能取值\n",
    "        dp = [[set() for _ in range(size)] for _ in range(size)] \n",
    "        \n",
    "        # 初始化 \n",
    "        for i in range(size):\n",
    "            dp[i][i] = [int(s[2*i])]\n",
    "        print(dp)\n",
    "\n",
    "        for k in range(2,size+1):     \n",
    "            # 区间长度 k:  取值 [2,size] （size=1于上文已经考虑）\n",
    "            for i in range(size-k+1): \n",
    "                # 区间开始位置 i, 对应区间 [i,i+k-1]; i 取值范围 [0,(size-k)]，\n",
    "                for j in range(i,i+k-1):    \n",
    "                    # 区间分割点j ,将区间分割为 [i,j]和[j+1,i+k-1] ； j取值为 [i,i+k-2]\n",
    "                    lst1 = dp[i][j]        #区间1可能取值\n",
    "                    lst2 = dp[j+1][i+k-1]  #区间2可能取值\n",
    "                    for e1 in lst1:\n",
    "                        for e2 in lst2:\n",
    "                            if s[2*j+1]==\"+\" and e1+e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1+e2)\n",
    "                            elif s[2*j+1]==\"*\" and e1*e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1*e2)\n",
    "        \n",
    "        # 分数计算\n",
    "        res = 0\n",
    "        for ans in answers:\n",
    "            if ans==true_ans:\n",
    "               res += 5\n",
    "            elif ans in dp[0][size-1]:\n",
    "                res += 2\n",
    "\n",
    "        \n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        # 计算实际的值\n",
    "        opd = []\n",
    "        i, n = 0, len(s)\n",
    "        while i < n:\n",
    "            if s[i] == '*':\n",
    "                i += 1\n",
    "                opd.append(opd.pop() * int(s[i]))\n",
    "            elif s[i] != '+':\n",
    "                opd.append(int(s[i]))\n",
    "            i += 1\n",
    "        real = sum(opd)\n",
    "        # 动态规划计算所有可能的解\n",
    "        dp = [[set() for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(0, n, 2):\n",
    "            dp[i][i].add(int(s[i]))  # 初始化长度为1的子表达式值\n",
    "        for width in range(3, n + 1, 2):  # 遍历所有子表达式的宽度\n",
    "            for left in range(0, n - width + 1, 2):  # 子表达式的左边界\n",
    "                right = left + width - 1  # 子表达式的右边界\n",
    "                for mid in range(left + 1, right, 2):  # 切分子表达式的操作符下标\n",
    "                    if s[mid] == '+':  # 计算dp[left][mid-1]、dp[mid+1][right]2个集合中所有元素的和\n",
    "                        for a in dp[left][mid - 1]:\n",
    "                            for b in dp[mid + 1][right]:\n",
    "                                if a + b <= 1000:  # 剪枝，可以筛掉很多\n",
    "                                    dp[left][right].add(a + b)\n",
    "                    else:  # 计算dp[left][mid-1]、dp[mid+1][right]2个集合中所有元素的乘积\n",
    "                        for a in dp[left][mid - 1]:\n",
    "                            for b in dp[mid + 1][right]:\n",
    "                                if a * b <= 1000:  # 剪枝，可以筛掉很多，不加这个筛选会超时\n",
    "                                    dp[left][right].add(a * b)\n",
    "        all = dp[0][n - 1]\n",
    "        # 计算结果\n",
    "        return sum(5 if a == real else (2 if a in all else 0) for a in answers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        # 计算实际的值\n",
    "        opd = []\n",
    "        i, n = 0, len(s)\n",
    "        while i < n:\n",
    "            if s[i] == '*':\n",
    "                i += 1\n",
    "                opd.append(opd.pop() * int(s[i]))\n",
    "            elif s[i] != '+':\n",
    "                opd.append(int(s[i]))\n",
    "            i += 1\n",
    "        real = sum(opd)\n",
    "        # 动态规划计算所有可能的解\n",
    "        dp = [[set() for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(0, n, 2):\n",
    "            dp[i][i].add(int(s[i]))  # 初始化长度为1的子表达式值\n",
    "        for width in range(3, n + 1, 2):  # 遍历所有子表达式的宽度\n",
    "            for left in range(0, n - width + 1, 2):  # 子表达式的左边界\n",
    "                right = left + width - 1  # 子表达式的右边界\n",
    "                for mid in range(left + 1, right, 2):  # 切分子表达式的操作符下标\n",
    "                    if s[mid] == '+':  # 计算dp[left][mid-1]、dp[mid+1][right]2个集合中所有元素的和\n",
    "                        for a in dp[left][mid - 1]:\n",
    "                            for b in dp[mid + 1][right]:\n",
    "                                if a + b <= 1000:  # 剪枝，可以筛掉很多\n",
    "                                    dp[left][right].add(a + b)\n",
    "                    else:  # 计算dp[left][mid-1]、dp[mid+1][right]2个集合中所有元素的乘积\n",
    "                        for a in dp[left][mid - 1]:\n",
    "                            for b in dp[mid + 1][right]:\n",
    "                                if a * b <= 1000:  # 剪枝，可以筛掉很多，不加这个筛选会超时\n",
    "                                    dp[left][right].add(a * b)\n",
    "        all = dp[0][n - 1]\n",
    "        # 计算结果\n",
    "        return sum(5 if a == real else (2 if a in all else 0) for a in answers)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        # 计算实际的值\n",
    "        n = len(s)\n",
    "        real = eval(s)\n",
    "        # 动态规划计算所有可能的解\n",
    "        dp = [[set() for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(0, n, 2):\n",
    "            dp[i][i].add(int(s[i]))  # 初始化长度为1的子表达式值\n",
    "        for width in range(3, n + 1, 2):  # 遍历所有子表达式的宽度\n",
    "            for left in range(0, n - width + 1, 2):  # 子表达式的左边界\n",
    "                right = left + width - 1  # 子表达式的右边界\n",
    "                for mid in range(left + 1, right, 2):  # 切分子表达式的操作符下标\n",
    "                    if s[mid] == '+':  # 计算dp[left][mid-1]、dp[mid+1][right]2个集合中所有元素的和\n",
    "                        for a in dp[left][mid - 1]:\n",
    "                            for b in dp[mid + 1][right]:\n",
    "                                if a + b <= 1000:  # 剪枝，可以筛掉很多\n",
    "                                    dp[left][right].add(a + b)\n",
    "                    else:  # 计算dp[left][mid-1]、dp[mid+1][right]2个集合中所有元素的乘积\n",
    "                        for a in dp[left][mid - 1]:\n",
    "                            for b in dp[mid + 1][right]:\n",
    "                                if a * b <= 1000:  # 剪枝，可以筛掉很多，不加这个筛选会超时\n",
    "                                    dp[left][right].add(a * b)\n",
    "        all = dp[0][n - 1]\n",
    "        # 计算结果\n",
    "        return sum(5 if a == real else (2 if a in all else 0) for a in answers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type answers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)  # 表达式长度\n",
    "        # 计算正确答案\n",
    "        stack = [int(s[0])]\n",
    "        i = 1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]==\"*\":\n",
    "                pre = stack.pop()\n",
    "                stack.append(pre*int(s[i+1]))\n",
    "            else:\n",
    "                stack.append(int(s[i+1]))\n",
    "            print(stack)\n",
    "        true_ans = sum(stack)\n",
    "        \n",
    "        # 表达式中包含的数字数量\n",
    "        size = (n+1)//2     \n",
    "        # 状态空间： dp[i][j] 表示第i个数字-第j个数字（包含首位）的表达式的可能取值\n",
    "        dp = [[set() for _ in range(size)] for _ in range(size)] \n",
    "        for i in range(size):\n",
    "            dp[i][i] = [int(s[2*i])]\n",
    "        print(dp)\n",
    "\n",
    "        for k in range(2,size+1):     \n",
    "            # 区间长度 k:  取值 [2,size] （size=1于上文已经考虑）\n",
    "            for i in range(size-k+1): \n",
    "                # 区间开始位置 i, 对应区间 [i,i+k-1]; i 取值范围 [0,(size-k)]，\n",
    "                for j in range(i,i+k-1):    \n",
    "                    # 区间分割点j ,将区间分割为 [i,j]和[j+1,i+k-1] ； j取值为 [i,i+k-2]\n",
    "                    lst1 = dp[i][j]        #区间1可能取值\n",
    "                    lst2 = dp[j+1][i+k-1]  #区间1可能取值\n",
    "                    for e1 in lst1:\n",
    "                        for e2 in lst2:\n",
    "                            if s[2*j+1]==\"+\" and e1+e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1+e2)\n",
    "                            elif s[2*j+1]==\"*\" and e1*e2<=1000:\n",
    "                                dp[i][i+k-1].add(e1*e2)\n",
    "                            #print(dp)\n",
    "        \n",
    "        print(dp)\n",
    "        # 分数计算\n",
    "        dic = defaultdict(int)\n",
    "        res = 0\n",
    "        for ans in answers:\n",
    "            if ans==true_ans:\n",
    "               res += 5\n",
    "            else:\n",
    "                dic[ans] += 1 \n",
    "        print(dp[0][size-1])\n",
    "        for k,v in dic.items():\n",
    "            if k in dp[0][size-1]:\n",
    "                res += 2*v\n",
    "\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type answers: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)  # 表达式长度\n",
    "        # 计算正确答案\n",
    "        stack = [int(s[0])]\n",
    "        i = 1\n",
    "        for i in range(1,n,2):\n",
    "            if s[i]==\"*\":\n",
    "                pre = stack.pop()\n",
    "                stack.append(pre*int(s[i+1]))\n",
    "            else:\n",
    "                stack.append(int(s[i+1]))\n",
    "            print(stack)\n",
    "        true_ans = sum(stack)\n",
    "        \n",
    "        # 表达式中包含的数字数量\n",
    "        size = (n+1)//2     \n",
    "        # 状态空间： dp[i][j] 表示第i个数字-第j个数字（包含首位）的表达式的可能取值\n",
    "        dp = [[set() for _ in range(size)] for _ in range(size)] \n",
    "        for i in range(size):\n",
    "            dp[i][i] = [int(s[2*i])]   #初始化，对于i=j情况，能组成的值为其本身\n",
    "        print(dp)\n",
    "\n",
    "        for step in range(2,size+1):       #枚举步伐，不断增大，即 step = j-i\n",
    "            # 区间长度 step:  取值 [2,size] （size=1于上文已经考虑）\n",
    "            for i in range(size-step+1): \n",
    "                # 区间开始位置 i, 对应区间 [i,i+step-1]; i 取值范围 [0,(size-step)]，\n",
    "                for j in range(i,i+step-1):    \n",
    "                    # 区间分割点j ,将区间分割为 [i,j]和[j+1,i+step-1] ； j取值为 [i,i+step-2]\n",
    "                    lst1 = dp[i][j]        #区间1可能取值\n",
    "                    lst2 = dp[j+1][i+step-1]  #区间1可能取值\n",
    "                    for e1 in lst1:\n",
    "                        for e2 in lst2:\n",
    "                            if s[2*j+1]==\"+\" and e1+e2<=1000:\n",
    "                                dp[i][i+step-1].add(e1+e2)\n",
    "                            elif s[2*j+1]==\"*\" and e1*e2<=1000:\n",
    "                                dp[i][i+step-1].add(e1*e2)\n",
    "                            #print(dp)\n",
    "        \n",
    "        print(dp)\n",
    "        # 分数计算\n",
    "        dic = defaultdict(int)\n",
    "        res = 0\n",
    "        for ans in answers:\n",
    "            if ans==true_ans:\n",
    "               res += 5\n",
    "            else:\n",
    "                dic[ans] += 1 \n",
    "        print(dp[0][size-1])\n",
    "        for k,v in dic.items():\n",
    "            if k in dp[0][size-1]:\n",
    "                res += 2*v\n",
    "\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if len(state) == 1:\n",
    "                return set(state)\n",
    "            m = len(state)\n",
    "            cur = set()\n",
    "            for i in range(m):\n",
    "                if isinstance(state[i], str) and state[i] in \"+*\":\n",
    "                    op = state[i]\n",
    "                    pre = dfs(state[:i])\n",
    "                    post = dfs(state[i + 1:])\n",
    "                    for x in pre:\n",
    "                        for y in post:\n",
    "                            z = x + y if op == \"+\" else x * y\n",
    "                            if z <= 1000:\n",
    "                                cur.add(z)\n",
    "            return cur\n",
    "\n",
    "        lst = [int(w) if w.isnumeric() else w for w in s]\n",
    "        res = dfs(tuple(lst))\n",
    "        real = eval(s)\n",
    "        return sum(5 if w == real else 2 if w in res else 0 for w in answers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ops = {\"+\": add, \"*\": mul}\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "\n",
    "        lst = [int(w)  if w not in ops else w for w in s]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if len(state) == 1:\n",
    "                return set(state)\n",
    "            m = len(state)\n",
    "            cur = set()\n",
    "            for i in range(m):\n",
    "                if state[i] in ops:\n",
    "                    op = state[i]\n",
    "                    pre = dfs(state[:i])\n",
    "                    post= dfs(state[i+1:])\n",
    "                    for x in pre:\n",
    "                        for y in post:\n",
    "                            z = ops[op](x, y)\n",
    "                            if z <= 1000:\n",
    "                                cur.add(z)\n",
    "            return cur\n",
    "        \n",
    "        res = dfs(tuple(lst))\n",
    "        real = eval(s)\n",
    "        return sum(5 if w == real else 2 if w in res else 0 for w in answers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from operator import add, mul\n",
    "\n",
    "# 使用操作符替代eval能极大提升效率\n",
    "#ops = {\"+\": add, \"*\": mul}\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if len(state) == 1:\n",
    "                return {int(state[0])}\n",
    "            res = set()\n",
    "            # 枚举最后一个运算符，从上至下进行递归，再从下而上返回计算值\n",
    "            for i in range(1, len(state), 2):\n",
    "                pre = dfs(state[:i])\n",
    "                post = dfs(state[i + 1:])\n",
    "                for a in pre:\n",
    "                    for b in post:\n",
    "                        #cur = ops[state[i]](a, b)\n",
    "                        if state[i] == '+':\n",
    "                            cur = a + b\n",
    "                        elif state[i] == '*':\n",
    "                            cur = a * b\n",
    "                        # 很关键的剪枝，不加入超出计算范围内的值\n",
    "                        if cur <= 1000:\n",
    "                            res.add(cur)\n",
    "            return res\n",
    "\n",
    "        # 很关键的一步，预先转换为整数方便计算\n",
    "        #lst = [int(va) if va not in ['+','*'] else va for va in list(s)]\n",
    "        #print(lst)\n",
    "        correct = eval(s)\n",
    "        res = dfs(tuple(s))\n",
    "        \n",
    "        ans = 0\n",
    "        for p in answers:\n",
    "            if p == correct:\n",
    "                ans += 5\n",
    "            elif p in res:\n",
    "                ans += 2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from operator import add, mul\n",
    "\n",
    "# 使用操作符替代eval能极大提升效率\n",
    "#ops = {\"+\": add, \"*\": mul}\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        #有这个语句，不会超出时间限制  \n",
    "        #存在同一状态的多次求值，所以使用记忆化递归，dfs递归加上这个，相同参数时不再重复计算，直接返回值\n",
    "        @lru_cache(None)     \n",
    "        def dfs(state):\n",
    "            if len(state) == 1:\n",
    "                return {int(state[0])}\n",
    "            res = set()\n",
    "            # 枚举最后一个运算符，从上至下进行递归，再从下而上返回计算值\n",
    "            for i in range(1, len(state), 2):\n",
    "                pre = dfs(state[:i])\n",
    "                post = dfs(state[i + 1:])\n",
    "                for a in pre:\n",
    "                    for b in post:\n",
    "                        #cur = ops[state[i]](a, b)\n",
    "                        if state[i] == '+':\n",
    "                            cur = a + b\n",
    "                        elif state[i] == '*':\n",
    "                            cur = a * b\n",
    "                        # 很关键的剪枝，不加入超出计算范围内的值\n",
    "                        if cur <= 1000:\n",
    "                            res.add(cur)\n",
    "            return res\n",
    "\n",
    "        # 很关键的一步，预先转换为整数方便计算\n",
    "        #lst = [int(va) if va not in ['+','*'] else va for va in list(s)]\n",
    "        #print(lst)\n",
    "        correct = eval(s)\n",
    "        res = dfs(tuple(s))\n",
    "        \n",
    "        ans = 0\n",
    "        for p in answers:\n",
    "            if p == correct:\n",
    "                ans += 5\n",
    "            elif p in res:\n",
    "                ans += 2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#from operator import add, mul\n",
    "\n",
    "# 使用操作符替代eval能极大提升效率\n",
    "#ops = {\"+\": add, \"*\": mul}\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if len(state) == 1:\n",
    "                return {state[0]}\n",
    "            res = set()\n",
    "            # 枚举最后一个运算符，从上至下进行递归，再从下而上返回计算值\n",
    "            for i in range(1, len(state), 2):\n",
    "                pre = dfs(state[:i])\n",
    "                post = dfs(state[i + 1:])\n",
    "                for a in pre:\n",
    "                    for b in post:\n",
    "                        #cur = ops[state[i]](a, b)\n",
    "                        if state[i] == '+':\n",
    "                            cur = a + b\n",
    "                        elif state[i] == '*':\n",
    "                            cur = a * b\n",
    "                        # 很关键的剪枝，不加入超出计算范围内的值\n",
    "                        if cur <= 1000:\n",
    "                            res.add(cur)\n",
    "            return res\n",
    "\n",
    "        # 很关键的一步，预先转换为整数方便计算\n",
    "        lst = [int(va) if va not in ['+','*'] else va for va in list(s)]\n",
    "        print(lst)\n",
    "        correct = eval(s)\n",
    "        res = dfs(tuple(lst))\n",
    "        \n",
    "        ans = 0\n",
    "        for p in answers:\n",
    "            if p == correct:\n",
    "                ans += 5\n",
    "            elif p in res:\n",
    "                ans += 2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import add, mul\n",
    "\n",
    "# 使用操作符替代eval能极大提升效率\n",
    "ops = {\"+\": add, \"*\": mul}\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if len(state) == 1:\n",
    "                return {state[0]}\n",
    "            res = set()\n",
    "            # 枚举最后一个运算符，从上至下进行递归，再从下而上返回计算值\n",
    "            for i in range(1, len(state), 2):\n",
    "                pre = dfs(state[:i])\n",
    "                post = dfs(state[i + 1:])\n",
    "                for a in pre:\n",
    "                    for b in post:\n",
    "                        cur = ops[state[i]](a, b)\n",
    "                        # 很关键的剪枝，不加入超出计算范围内的值\n",
    "                        if cur <= 1000:\n",
    "                            res.add(cur)\n",
    "            return res\n",
    "\n",
    "        # 很关键的一步，预先转换为整数方便计算\n",
    "        lst = [int(va) if va not in ops else va for va in list(s)]\n",
    "        print(lst)\n",
    "        correct = eval(s)\n",
    "        res = dfs(tuple(lst))\n",
    "        \n",
    "        ans = 0\n",
    "        for p in answers:\n",
    "            if p == correct:\n",
    "                ans += 5\n",
    "            elif p in res:\n",
    "                ans += 2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import add, mul\n",
    "\n",
    "# 使用操作符替代eval能极大提升效率\n",
    "ops = {\"+\": add, \"*\": mul}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if len(state) == 1:\n",
    "                return {state[0]}\n",
    "            res = set()\n",
    "            # 枚举最后一个运算符，从上至下进行递归，再从下而上返回计算值\n",
    "            for i in range(1, len(state), 2):\n",
    "                pre = dfs(state[:i])\n",
    "                post = dfs(state[i + 1:])\n",
    "                for a in pre:\n",
    "                    for b in post:\n",
    "                        cur = ops[state[i]](a, b)\n",
    "                        # 很关键的剪枝，不加入超出计算范围内的值\n",
    "                        if cur <= 1000:\n",
    "                            res.add(cur)\n",
    "            return res\n",
    "\n",
    "        # 很关键的一步，预先转换为整数方便计算\n",
    "        lst = [int(va) if va not in ops else va for va in list(s)]\n",
    "        true = eval(s)\n",
    "        res = dfs(tuple(lst))\n",
    "        return sum(5 if x == true else 2 for x in answers if x in res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import add, mul\n",
    "\n",
    "# 使用操作符替代eval能极大提升效率\n",
    "ops = {\"+\": add, \"*\": mul}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if len(state) == 1:\n",
    "                return {state[0]}\n",
    "            res = set()\n",
    "            # 枚举最后一个运算符，从上至下进行递归，再从下而上返回计算值\n",
    "            for i in range(1, len(state), 2):\n",
    "                pre = dfs(state[:i])\n",
    "                post = dfs(state[i + 1:])\n",
    "                for a in pre:\n",
    "                    for b in post:\n",
    "                        cur = ops[state[i]](a, b)\n",
    "                        # 很关键的剪枝，不加入超出计算范围内的值\n",
    "                        if cur <= 1000:\n",
    "                            res.add(cur)\n",
    "            return res\n",
    "\n",
    "        # 很关键的一步，预先转换为整数方便计算\n",
    "        lst = [int(va) if va not in ops else va for va in list(s)]\n",
    "        true = eval(s)\n",
    "        res = dfs(tuple(lst))\n",
    "        return sum(5 if x == true else 2 for x in answers if x in res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce, cache\r\n",
    "from itertools import product\r\n",
    "from collections import Counter\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\r\n",
    "        # dp[i][j] := valid answers after calculating op[i] to op[j]\r\n",
    "        # dp[i][j] = s[2 * i] if j <= i\r\n",
    "        # dp[i][j] = union(dp[i][k - 1] op[k] dp[k + 1][j]), i <= k <= j\r\n",
    "        #   i.e. choosing each operation as the last\r\n",
    "        @cache\r\n",
    "        def dp(i: int, j: int):\r\n",
    "            if j < i: return {ord(s[2 * i]) - 48}\r\n",
    "            return  reduce(lambda x, y: x | y,\r\n",
    "                        map(lambda k: {(a + b) if s[2 * k + 1] == \"+\" else (a * b) for a, b in product(dp(i , k - 1), dp(k + 1, j))\r\n",
    "                            if s[2 * k + 1] == \"+\" and (a + b) <= 1000 or s[2 * k + 1] == \"*\" and (a * b) <= 1000},\r\n",
    "                            range(i, j + 1)), set())\r\n",
    "        \r\n",
    "        vals, ans = dp(0, (len(s) >> 1) - 1), eval(s)\r\n",
    "        return sum((5 if a == ans else (2 if a in vals else 0)) * c for a, c in Counter(answers).items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        cnts = Counter(answers)\n",
    "\n",
    "        correct = eval(s)\n",
    "\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i == j:\n",
    "                return {int(s[i])}\n",
    "\n",
    "            ret = set()\n",
    "            for k in range(i + 1, j):\n",
    "                if s[k] == '+':\n",
    "                    a = dp(i, k - 1)\n",
    "                    b = dp(k + 1, j)\n",
    "\n",
    "                    for x in a:\n",
    "                        for y in b:\n",
    "                            if 0 <= x + y <= 1000:\n",
    "                                ret.add(x + y)\n",
    "\n",
    "                elif s[k] == '*':\n",
    "                    a = dp(i, k - 1)\n",
    "                    b = dp(k + 1, j)\n",
    "\n",
    "                    for x in a:\n",
    "                        for y in b:\n",
    "                            if 0 <= x * y <= 1000:\n",
    "                                ret.add(x * y)\n",
    "\n",
    "            return ret\n",
    "\n",
    "        n = len(s)\n",
    "        errs = dp(0, n - 1)\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        ret += cnts[correct] * 5\n",
    "\n",
    "        for x in errs:\n",
    "            if x != correct:\n",
    "                ret += cnts[x] * 2\n",
    "\n",
    "        return ret\n",
    "        \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        cnts = Counter(answers)\n",
    "        n = len(s)\n",
    "\n",
    "        st = []\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i].isdigit():\n",
    "                if i == 0 or s[i - 1] == '+':\n",
    "                    st.append(int(s[i]))\n",
    "                else:\n",
    "                    st[-1] *= int(s[i])\n",
    "\n",
    "        correct = sum(st)\n",
    "\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i == j:\n",
    "                return {int(s[i])}\n",
    "\n",
    "            ret = set()\n",
    "            for k in range(i + 1, j):\n",
    "                if s[k] == '+':\n",
    "                    a = dp(i, k - 1)\n",
    "                    b = dp(k + 1, j)\n",
    "\n",
    "                    for x in a:\n",
    "                        for y in b:\n",
    "                            if 0 <= x + y <= 1000:\n",
    "                                ret.add(x + y)\n",
    "\n",
    "                elif s[k] == '*':\n",
    "                    a = dp(i, k - 1)\n",
    "                    b = dp(k + 1, j)\n",
    "\n",
    "                    for x in a:\n",
    "                        for y in b:\n",
    "                            if 0 <= x * y <= 1000:\n",
    "                                ret.add(x * y)\n",
    "\n",
    "            return ret\n",
    "\n",
    "        \n",
    "        errs = dp(0, n - 1)\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        ret += cnts[correct] * 5\n",
    "\n",
    "        for x in errs:\n",
    "            if x != correct:\n",
    "                ret += cnts[x] * 2\n",
    "\n",
    "        return ret\n",
    "        \n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\r\n",
    "        n = len(s)\r\n",
    "        # number of operators\r\n",
    "        m = n >> 1\r\n",
    "        # dp[i][j] := valid answers after calculating op[i] to op[j]\r\n",
    "        # dp[i][j] = s[2 * i] if j <= i\r\n",
    "        # dp[i][j] = union(dp[i][k - 1] op[k] dp[k + 1][j]), i <= k <= j\r\n",
    "        #   i.e. choosing each operation as the last\r\n",
    "        dp: list[list[set[int]]] = [[set() for _ in range(m)] for __ in range(m)]\r\n",
    "\r\n",
    "        def dfs(i: int, j: int):\r\n",
    "            if j < i:\r\n",
    "                yield ord(s[2 * i]) - 48\r\n",
    "            else:\r\n",
    "                if not dp[i][j]:\r\n",
    "                    for k in range(i, j + 1):\r\n",
    "                        for a in dfs(i, k - 1):\r\n",
    "                            for b in dfs(k + 1, j):\r\n",
    "                                if s[2 * k + 1] == \"+\":\r\n",
    "                                    if a + b <= 1000:\r\n",
    "                                        dp[i][j].add(a + b)\r\n",
    "                                elif a * b <= 1000:\r\n",
    "                                    dp[i][j].add(a * b)\r\n",
    "                yield from dp[i][j]\r\n",
    "        \r\n",
    "        _ = list(dfs(0, m - 1))\r\n",
    "        ans = eval(s)\r\n",
    "        return sum(map(lambda i: 5 if i == ans else (2 if i in dp[0][m - 1] else 0), answers))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s, answers):\n",
    "        mx_ans = max(answers)\n",
    "        nums, ops = [], []\n",
    "        x, o = [], []\n",
    "        for ch in s:\n",
    "            if ch == '*':\n",
    "                ops.append(ch)\n",
    "                o.append(ch)\n",
    "            elif ch == '+':\n",
    "                while len(ops):\n",
    "                    n1 = nums.pop(-1)\n",
    "                    n2 = nums.pop(-1)\n",
    "                    nums.append(n1 + n2)\n",
    "                    ops.pop(-1)\n",
    "                o.append(ch)\n",
    "            else:\n",
    "                x.append(int(ch))\n",
    "                if len(ops) and ops[-1] == '*':\n",
    "                    n1 = int(ch)\n",
    "                    n2 = nums.pop(-1)\n",
    "                    nums.append(n1 * n2)\n",
    "                    ops.pop(-1)\n",
    "                else:\n",
    "                    nums.append(int(ch))\n",
    "        corr_ans = sum(nums)\n",
    "        n = len(x)\n",
    "        dp = [[set() for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i].add(x[i])\n",
    "        \n",
    "        def work(i, j):\n",
    "            if len(dp[i][j]) > 0:\n",
    "                return dp[i][j]\n",
    "            if j > 0 and x[j] == 0 and o[j - 1] == '*':\n",
    "                dp[i][j].add(0)\n",
    "            for k in range(i, j):\n",
    "                r1 = work(i, k)\n",
    "                r2 = work(k + 1, j)\n",
    "                for z1 in r1:\n",
    "                    for z2 in r2:\n",
    "                        if o[k] == '+':\n",
    "                            z3 = z1 + z2\n",
    "                        else:\n",
    "                            z3 = z1 * z2\n",
    "                        if z3 <= mx_ans:\n",
    "                            dp[i][j].add(z3)\n",
    "            return dp[i][j]\n",
    "        \n",
    "        work(0, len(x) - 1)\n",
    "        ret = 0\n",
    "        for a in answers:\n",
    "            if a == corr_ans:\n",
    "                ret += 5\n",
    "            elif a in dp[0][len(x) - 1]:\n",
    "                ret += 2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        @lru_cache\n",
    "        def myfunc(exp):\n",
    "            if exp.isdigit():\n",
    "                return {int(exp)}\n",
    "            \n",
    "            res = set()\n",
    "            for i, ch in enumerate(exp):\n",
    "                if ch in '*+':\n",
    "                    left = myfunc(exp[: i])\n",
    "                    right = myfunc(exp[i + 1: ])\n",
    "                    for l in left:\n",
    "                        for r in right:\n",
    "                            if ch == '*':\n",
    "                                one = l * r\n",
    "                            else:\n",
    "                                one = l + r\n",
    "                            if one <= 1000:\n",
    "                                res.add(one)\n",
    "            return res\n",
    "        \n",
    "        correct = eval(s)\n",
    "        res = myfunc(s)\n",
    "        ans = 0\n",
    "        for answer in answers:\n",
    "            score = 0\n",
    "            if answer == correct:\n",
    "                score = 5\n",
    "            elif answer in res:\n",
    "                score = 2\n",
    "            else:\n",
    "                score = 0\n",
    "            ans += score\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        @lru_cache\n",
    "        def myfunc(exp):\n",
    "            if exp.isdigit():\n",
    "                return {int(exp)}\n",
    "            \n",
    "            res = set()\n",
    "            for i, ch in enumerate(exp):\n",
    "                if ch in '*+':\n",
    "                    left = myfunc(exp[: i])\n",
    "                    right = myfunc(exp[i + 1: ])\n",
    "                    for l in left:\n",
    "                        for r in right:\n",
    "                            if ch == '*':\n",
    "                                one = l * r\n",
    "                            else:\n",
    "                                one = l + r\n",
    "                            #print(type(one))\n",
    "                            if one <= 1000:\n",
    "                                res.add(one)\n",
    "            return res\n",
    "        \n",
    "        correct = eval(s)\n",
    "        res = myfunc(s)\n",
    "        ans = 0\n",
    "        for answer in answers:\n",
    "            score = 0\n",
    "            if answer == correct:\n",
    "                score = 5\n",
    "            elif answer in res:\n",
    "                score = 2\n",
    "            else:\n",
    "                score = 0\n",
    "            ans += score\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        right_value = eval(s)\n",
    "        \n",
    "        @cache\n",
    "        def f(s):\n",
    "            if s.isdigit():\n",
    "                return {int(s)}\n",
    "            ans = set()\n",
    "            for i, c in enumerate(s):\n",
    "                if c == '+':\n",
    "                    lefts = f(s[:i])\n",
    "                    rights = f(s[i+1:])\n",
    "                    for l in lefts:\n",
    "                        for r in rights:\n",
    "                            if l + r <= 1000:\n",
    "                                ans.add(l+r)\n",
    "                elif c == '*':\n",
    "                    lefts = f(s[:i])\n",
    "                    rights = f(s[i+1:])\n",
    "                    for l in lefts:\n",
    "                        for r in rights:\n",
    "                            if l * r <= 1000:\n",
    "                                ans.add(l*r)\n",
    "            return ans\n",
    "        \n",
    "        sett = f(s)\n",
    "        ans = 0\n",
    "        for x in answers:\n",
    "            if x == right_value:\n",
    "                ans += 5\n",
    "            elif x in sett:\n",
    "                ans += 2\n",
    "        \n",
    "        return ans\n",
    "  \n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "op = {'+': add, '*': mul}\n",
    "@lru_cache(None)\n",
    "def dfs(s):\n",
    "    return {s[0]} if len(s) == 1 else\\\n",
    "           set([op[s[i]](a, b) for i in range(1, len(s), 2) for a in dfs(s[:i]) for b in dfs(s[i + 1:]) if op[s[i]](a, b) <= 1000])\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        correct = eval(s)\n",
    "        d = dfs(tuple(ch if ch in ('+', '*') else int(ch) for ch in s))\n",
    "        return sum(5 if x == correct else 2 for x in answers if x in d)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from operator import add, mul\n",
    "\n",
    "op = {'+': add, '*': mul}\n",
    "\n",
    "@lru_cache(None)\n",
    "def dfs(s):\n",
    "    # Base case: if string length is 1, return the integer form of the string\n",
    "    if len(s) == 1:\n",
    "        return {s[0]}\n",
    "    # Recursive case: calculate all possible results by considering different operations\n",
    "    return set([op[s[i]](a, b) for i in range(1, len(s), 2) for a in dfs(s[:i]) for b in dfs(s[i + 1:]) if op[s[i]](a, b) <= 1000])\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfStudents(self, s: str, answers: List[int]) -> int:\n",
    "        # Compute the correct answer of the expression\n",
    "        correct = eval(s)\n",
    "        # Get all possible answers by considering different operation orders\n",
    "        d = dfs(tuple(ch if ch in ('+', '*') else int(ch) for ch in s))\n",
    "        # Calculate the total score based on the answers of the students\n",
    "        return sum(5 if x == correct else 2 for x in answers if x in d)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
